		
		#include "../include/BST.h"
		
		
		
		int bstInsertNode(struct bstNode **rootNode,fd *data)
		{

			

			struct bstNode * temp1 = NULL;
			struct Index *q;
			struct bstNode *p ;
			struct bstNode * temp2 = NULL;
		
		
			 q=(struct Index*)malloc(sizeof(struct Index));
		
		
		
			p=(struct bstNode*)malloc(sizeof(struct bstNode));
		
			
		
		
			
			char *buffer = malloc (strlen (data->file_name) + strlen (data->path) + 2);
			if (buffer == NULL) {
		    	// Out of memory.
			}
		 	else {
		    	strcpy (buffer, data->path);

			if(strcmp(buffer,"/")!=0)
			    	strcat (buffer,"/");

		    	strcat (buffer,data->file_name);
		    
			}
			q->key=buffer;
		
			q->data = data;
		
			
			
			if((*rootNode) == NULL)
			{
				p->data = q;
				
				p->leftChild = p->rightChild= NULL;
				(*rootNode) = p;
				//printf("\nSuccessful insertion :%s",p->data->key);
				return 0;
		
			
		
			}
			else
			{
			
			
			p = *rootNode;
			temp1 = p;
			while(temp1 != NULL)
			{
				temp2 = temp1;
				if(strcmp(temp1->data->key, q->key) == 0)
				{
					
					//printf("\n%s is a Duplicate Key",temp1->data->key);
					return 1;
				}
				else
				{
					if(strcmp(temp1->data->key, q->key) > 0)
					{ 
						temp1 = temp1->leftChild;
					}
					else
					{
						temp1 = temp1->rightChild;
					}
				}
		
			}
		
			}
		
			
		
			if(strcmp(temp2->data->key, q->key) > 0)
			{
				temp2->leftChild= (struct bstNode *)malloc(sizeof(struct bstNode));
				temp2 = temp2->leftChild;
				temp2->data= q;
				temp2->leftChild = temp2->rightChild = NULL;
				//printf("\nSuccessful insertion: %s\n",temp2->data->key);
				return 0;
			}
		
		
			else
			{	
				temp2->rightChild= (struct bstNode *)malloc(sizeof(struct bstNode));
				temp2 = temp2->rightChild;
				temp2->data = q;
				temp2->leftChild = temp2->rightChild = NULL;
				//printf("\nSuccessful insertion: %s\n",temp2->data->key);
				
				return 0;
			}
		
			
		
		}
		
		
		fd * bstSearchNode(struct bstNode **rootNode,char *fullpath)
		{
			struct bstNode * temp = *rootNode;
			fd *searchedNode = (fd*) malloc(sizeof(fd));
			
			char *key = malloc (strlen(fullpath) + 2);
			if (key == NULL) {
		    	// Out of memory.
			} 	else {

		    	strcpy (key, fullpath);
		    	//strcat (key,"/");
		    	//strcat (key,file_name);
		    
			}
		
			while(temp != NULL)
			{
				if((strcmp(temp->data->key,key) == 0))
										
				{	
						//printf("\n%s Key is found ",temp->data->key);
						searchedNode = temp->data->data;
					//	printf("***************searchnode in bst=%s************",temp->data->data->file_name);
						return searchedNode;
					}
				
				else
				{
					if(strcmp(temp->data->key,key) > 0)
					{
						temp = temp->leftChild;
					}
					else
					{
						temp =  temp->rightChild;
					}
				}
		
			}
			//printf("\n%s Key not found\n",key);
			return NULL;
		}
		
		
		
		
		int bstDeleteNode(struct bstNode **rootNode,char* fullpath)
		{
			struct bstNode *cur,*parent,*suc,*q,*p;
			char *key = malloc (strlen (fullpath)  + 2);
			if (key == NULL) {
		    	// Out of memory.
		}
	 	else {
		    	strcpy (key, fullpath);
		    	//strcat (key,"/");
		    	//strcat (key,file_name);
		    
		}
		
			if(*rootNode==NULL)
			{
				//printf("\ntree is empty!");
				return 1;
			}
			parent=NULL, cur=*rootNode;
			
			if((strcmp(key,cur->data->key) == 0) && cur->leftChild==NULL && cur->rightChild==NULL)
			{
				free(cur);
				(*rootNode) = NULL;
				//printf("\n%s is deleted(source)",key);
				return 0;
			}
			
			while( cur!=NULL)
			{
				if(strcmp(key,cur->data->key) == 0) break;
				parent=cur;
				cur=(strcmp(key,cur->data->key) < 0)? cur->leftChild:cur->rightChild;
			}
			
			if(cur==NULL)
			{
				//printf("\n%s is not found",key);
				return 0;
			}
			
			if(cur->leftChild==NULL)
				q=cur->rightChild;
			else if(cur->rightChild==NULL)
				q=cur->leftChild;
			else
			{
				suc=cur->rightChild;		/*obtain inorder successor*/
		
				while(suc->leftChild!=NULL)
					suc=suc->leftChild;
				suc->leftChild=cur->leftChild;
		
				q=cur->rightChild;
			}
		
			if(parent==NULL)
			{ 
				
				while(q != NULL)		
				{	p = q;
					q = q->leftChild;
				}
				
				p->leftChild = NULL;
		
				*rootNode = suc;
			
				free(q);
				//printf("\n%s is deleted(source)",key);
				return 1;
			}
		
			/*connecting parent of the nod eto be deleted to q*/
		
			if(cur==parent->leftChild)
				parent->leftChild=q;
			else
				parent->rightChild=q;
			free(cur);
			//printf("\n%s is deleted",key);
			return 1;
		
		
		
		}
		
		//printtree
		
		void print(struct bstNode *T)
		{
			if(T==NULL)
			{return;}
			else{
			
			print(T->leftChild);
			//printf("\n%s",T->data->key);
			print(T->rightChild);}
		}
		
		
	
